{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关联分析的基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关联分析（Association Analysis）：在大规模数据集中寻找有趣的关系。\n",
    "\n",
    "频繁项集（Frequent Item Sets）：经常出现在一块的物品的集合，即包含0个或者多个项的集合称为项集。\n",
    "\n",
    "支持度（Support）：数据集中包含该项集的记录所占的比例，是针对项集来说的。\n",
    "\n",
    "置信度（Confidence）：出现某些物品时，另外一些物品必定出现的概率，针对规则而言。\n",
    "\n",
    "关联规则（Association Rules）：暗示两个物品之间可能存在很强的关系。形如A->B的表达式，规则A->B的度量包括支持度和置信度\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 项集支持度：一个项集出现的次数与数据集所有事物数的百分比称为项集的支持度\n",
    "\n",
    "$eg: support(A\\Rightarrow B) = support\\_count(A∪ B) / N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">支持度反映了A和B同时出现的概率，关联规则的支持度等于频繁集的支持度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 项集置信度：包含A的数据集中包含B的百分比\n",
    "\n",
    "$eg: confidence(A\\Rightarrow B) = support\\_count(A∪B ) / support\\_count(A)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">置信度反映了如果交易中包含A，则交易包含B的概率。也可以称为在A发生的条件下，发生B的概率，成为条件概率。\n",
    "\n",
    "**只有支持度和置信度(可信度)较高的关联规则才是用户感兴趣的。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关联分析步骤\n",
    "\n",
    "1、发现频繁项集，即计算所有可能组合数的支持度，找出不少于人为设定的最小支持度的集合。\n",
    "\n",
    "2、发现关联规则，即计算不小于人为设定的最小支持度的集合的置信度，找到不小于认为设定的最小置信度规则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关联分析的两种关系：简单关联关系和序列关联关系\n",
    "\n",
    "\n",
    "**简单关联关系：**\n",
    "\n",
    "简单关联关系可以从经典的购物中进行分析，购买面包的顾客80%都会购买牛奶，由于面包和牛奶是早餐搭配的必需品，二者搭配构成了早餐的组成部分，这就是一种简单的关联关系。\n",
    "\n",
    "**序列关联关系：**\n",
    "\n",
    "当购买一款新手机后，就会考虑去购买手机膜等手机配件，这就是一种序列关系，不会先买手机膜再买手机的，先后关系是非常明显的，这种关系是一种顺序性的关系，也就是一种序列关联关系。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">关联规则：规则就是一种衡量事物的标准，也就是一个算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 简单关联规则算法\n",
    "\n",
    "\n",
    "**算法思想基础**\n",
    "\n",
    "> 如果某个项集是频繁的，那么它的所有子集也是频繁的。更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的。\n",
    "\n",
    "简单关联规则是无指导的学习方法，着重探索内部结构。\n",
    "\n",
    "简单关联规则也是使用最多的技术，主要算法包括：Apriori、GRI、Carma，其中Apriori和Carma主要是如何提高关联规则的分析效率，而GRI注重如何将单一概念层次的关联推广到更多概念层次的关联，进而揭示事物内在结构。\n",
    "\n",
    "简单关联规则的数据存储形式：**一种是交易数据格式，一种是表格数据格式。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 序列关联规则算法\n",
    "\n",
    "\n",
    "序列关联规则的核心就是找到事物发展的前后关联性，研究序列关联可以来推测事物未来的发展情况，并根据预测的发展情况进行事物的分配和安排。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 如何设定合理的支持度和置信度？\n",
    "\n",
    "\n",
    "对于某条规则："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$（A=a）->（B=b）$（support=30%,confident=60%）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中：support=30%表示在所有的数据记录中，同时出现A=a和B=b的概率为30%；confident=60%表示在所有的数据记录中，在出现A=a的情况下出现B=b的概率为60%，也就是条件概率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "支持度揭示了A=a和B=b同时出现的概率，置信度揭示了当A=a出现时，B=b是否会一定出现的概率。\n",
    "\n",
    "（1）如果支持度和置信度闭值设置的过高，虽然可以减少挖掘时间，但是容易造成一些隐含在数据中非频繁特征项被忽略掉，难以发现足够有用的规则；\n",
    "\n",
    "（2）如果支持度和置信度闭值设置的过低，又有可能产生过多的规则，甚至产生大量冗余和无效的规则，同时由于算法存在的固有问题，会导致高负荷的计算量，大大增加挖掘时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关联分析的应用\n",
    "\n",
    "\n",
    "(1)：购物篮分析，通过查看那些商品经常在一起出售，可以帮助商店了解用户的购物行为，这种从数据的海洋中抽取只是可以用于商品定价、市场促销、存货管理等环节\n",
    "\n",
    "(2)：在Twitter源中发现一些公共词。对于给定的搜索词，发现推文中频繁出现的单词集合\n",
    "\n",
    "(3)：从新闻网站点击流中挖掘新闻流行趋势，挖掘哪些新闻广泛被用户浏览到\n",
    "\n",
    "(4)：搜索引擎推荐，在用户输入查询时推荐同时相关的查询词项\n",
    "\n",
    "(5)：发现毒蘑菇的相似特征。这里只对包含某个特征元素（有毒素）的项集感兴趣，从中寻找毒蘑菇中的一些公共特征，利用这些特征来避免迟到哪些有毒的蘑菇\n",
    "\n",
    "(6)：图书馆信息的书籍推荐，对于学生的借书信息，不同专业学生的借书情况，来挖掘不同学生的借书情况，进行数目的推荐。\n",
    "\n",
    "(7)：校园网新闻通知信息的推荐，在对校园网新闻通知信息进行挖掘的过程中，分析不同部门，不同学院的新闻信息的不同，在进行新闻信息浏览的过程中进行新闻的推荐。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Apriori算法\n",
    "\n",
    "假设我们有一家经营着4种商品（商品0，商品1，商品2和商品3）的杂货店，图显示了所有商品之间所有的可能组合：\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/b1f028a42896f438e9c65c0269f86701.png)\n",
    "\n",
    "对于单个项集的支持度，我们可以通过遍历每条记录并检查该记录是否包含该项集来计算。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于包含N中物品的数据集共有$2^N−1$种项集组合，重复上述计算过程是不现实的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "研究人员通过这个假设，发现了一种所谓的Apriori原理，可以帮助我们减少计算量。\n",
    "\n",
    ">Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。\n",
    "\n",
    ">**例如一个频繁项集包含3个项A、B、C，则这三个项组成的子集{A},{B},{C},{A、B}，{A、C}、{B、C}一定是频繁项集。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不过更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在图中，已知阴影项集{2,3}是非频繁的。利用这个知识，我们就知道项集{0,2,3}，{1,2,3}以及{0,1,2,3}也是非频繁的。\n",
    "\n",
    "也就是说，一旦计算出了{2,3}的支持度，知道它是非频繁的后，就可以紧接着排除{0,2,3}、{1,2,3}和{0,1,2,3}。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/d1bcafdae1376b959cbc2c83f69c5d9c.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">Apriori算法是发现**频繁项集**的一种方法。并不会找出关联规则，关联规则需要在找到频繁项集以后我们再来统计。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Apriori算法的两个输入参数分别是最小支持度和数据集。\n",
    "\n",
    "\n",
    "该算法首先会生成所有单个元素的项集列表。\n",
    "\n",
    "接着扫描数据集来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉。\n",
    "\n",
    "然后，对剩下来的集合进行组合以生成包含两个元素的项集。\n",
    "\n",
    "接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "该算法需要不断寻找候选集，然后剪枝即去掉非频繁子集的候选集，时间复杂度由暴力枚举所有子集的指数级别$O（n^2）$降为多项式级别，"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Ariori算法有两个主要步骤：\n",
    "\n",
    "1、连接：（将项集进行两两连接形成新的候选集）\n",
    "\n",
    "利用已经找到的$k$个项的频繁项集$L_k$，通过两两连接得出候选集$C_{k+1}$，注意进行连接的$L_k[i]$，$L_k[j]$，必须有$k-1个$属性值相同，然后另外两个不同的分别分布在$L_k[i]$，$L_k[j]$中，这样的求出的$C_{k+1}$为$L_{k+1}$的候选集。\n",
    "\n",
    "2、剪枝：（去掉非频繁项集）\n",
    "\n",
    "候选集 $C_{k+1}$中的并不都是频繁项集，必须剪枝去掉，越早越好以防止所处理的数据无效项越来越多。\n",
    "\n",
    "**只有当子集都是频繁集的候选集才是频繁集，这是剪枝的依据**。\n",
    "      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "算法实现\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Looking in indexes: https://mirrors.tencent.com/pypi/simple/, https://mirrors.tencent.com/repository/pypi/tencent_pypi/simple\n",
      "Requirement already satisfied: numpy in /usr/local/lib/python3.8/dist-packages (1.22.1)\n",
      "\u001b[33mWARNING: Running pip as the 'root' user can result in broken permissions and conflicting behaviour with the system package manager. It is recommended to use a virtual environment instead: https://pip.pypa.io/warnings/venv\u001b[0m\u001b[33m\n",
      "\u001b[0m"
     ]
    }
   ],
   "source": [
    "! pip install numpy\n",
    "from numpy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def loadDataSet():\n",
    "    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]\n",
    "\n",
    "# 获取候选1项集，dataSet为事务集。返回一个list，每个元素都是set集合\n",
    "def createC1(dataSet):\n",
    "    C1 = []   # 元素个数为1的项集（非频繁项集，因为还没有同最小支持度比较）\n",
    "    for transaction in dataSet:\n",
    "        for item in transaction:\n",
    "            if not [item] in C1:\n",
    "                C1.append([item])\n",
    "    C1.sort()  # 这里排序是为了，生成新的候选集时可以直接认为两个n项候选集前面的部分相同\n",
    "    # 因为除了候选1项集外其他的候选n项集都是以二维列表的形式存在，所以要将候选1项集的每一个元素都转化为一个单独的集合。\n",
    "    return list(map(frozenset, C1))   #map(frozenset, C1)的语义是将C1由Python列表转换为不变集合（frozenset，Python中的数据结构）\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 找出候选集中的频繁项集\n",
    "# dataSet为全部数据集，Ck为大小为k（包含k个元素）的候选项集，minSupport为设定的最小支持度\n",
    "def scanD(dataSet, Ck, minSupport):\n",
    "    ssCnt = {}   # 记录每个候选项的个数\n",
    "    for tid in dataSet:\n",
    "        for can in Ck:\n",
    "            if can.issubset(tid):\n",
    "                ssCnt[can] = ssCnt.get(can, 0) + 1   # 计算每一个项集出现的频率\n",
    "    numItems = float(len(dataSet))\n",
    "    retList = []\n",
    "    supportData = {}\n",
    "    for key in ssCnt:\n",
    "        support = ssCnt[key] / numItems\n",
    "        if support >= minSupport:\n",
    "            retList.insert(0, key)  #将频繁项集插入返回列表的首部\n",
    "        supportData[key] = support\n",
    "    return retList, supportData   #retList为在Ck中找出的频繁项集（支持度大于minSupport的），supportData记录各频繁项集的支持度\n",
    "\n",
    "\n",
    "# 通过频繁项集列表Lk和项集个数k生成候选项集C(k+1)。\n",
    "def aprioriGen(Lk, k):\n",
    "    retList = []\n",
    "    lenLk = len(Lk)\n",
    "    for i in range(lenLk):\n",
    "        for j in range(i + 1, lenLk):\n",
    "            # 前k-1项相同时，才将两个集合合并，合并后才能生成k+1项\n",
    "            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]   # 取出两个集合的前k-1个元素\n",
    "            L1.sort(); L2.sort()\n",
    "            if L1 == L2:\n",
    "                retList.append(Lk[i] | Lk[j])\n",
    "    return retList\n",
    "\n",
    "# 获取事务集中的所有的频繁项集\n",
    "# Ck表示项数为k的候选项集，最初的C1通过createC1()函数生成。Lk表示项数为k的频繁项集，supK为其支持度，Lk和supK由scanD()函数通过Ck计算而来。\n",
    "def apriori(dataSet, minSupport=0.5):\n",
    "    C1 = createC1(dataSet)  # 从事务集中获取候选1项集\n",
    "    D = list(map(set, dataSet))  # 将事务集的每个元素转化为集合\n",
    "    L1, supportData = scanD(D, C1, minSupport)  # 获取频繁1项集和对应的支持度\n",
    "    L = [L1]  # L用来存储所有的频繁项集\n",
    "    k = 2\n",
    "    while (len(L[k-2]) > 0): # 一直迭代到项集数目过大而在事务集中不存在这种n项集\n",
    "        Ck = aprioriGen(L[k-2], k)   # 根据频繁项集生成新的候选项集。Ck表示项数为k的候选项集\n",
    "        Lk, supK = scanD(D, Ck, minSupport)  # Lk表示项数为k的频繁项集，supK为其支持度\n",
    "        L.append(Lk);supportData.update(supK)  # 添加新频繁项集和他们的支持度\n",
    "        k += 1\n",
    "    return L, supportData\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[frozenset({5}), frozenset({2}), frozenset({3})], [frozenset({2, 5})], []] {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5}\n"
     ]
    }
   ],
   "source": [
    "dataSet = loadDataSet()  # 获取事务集。每个元素都是列表\n",
    "# C1 = createC1(dataSet)  # 获取候选1项集。每个元素都是集合\n",
    "# D = list(map(set, dataSet))  # 转化事务集的形式，每个元素都转化为集合。\n",
    "# L1, suppDat = scanD(D, C1, 0.5)\n",
    "# print(L1,suppDat)\n",
    "\n",
    "\n",
    "L, suppData = apriori(dataSet,minSupport=0.7)\n",
    "print(L,suppData)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
